package 完全背包问题;

/**
 * @Date 2024/6/3 17:27
 * @description: 力扣322: 零钱兑换(完全背包问题)
 * .        https://leetcode.cn/problems/coin-change/
 * @Author LittleNight
 */
public class likou322 {

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        // 完全背包: 前 i 个物品中挑选，背包容量不超过 j 时，所有的选法中, 最大的价值是多少
        // 完全背包: 前 i 个硬币中挑选，总金额恰好等于 j 时，所有的选法中, 最小的硬币数是多少
        int[][] dp = new int[n + 1][amount + 1];
        // 恰好问题, 需要初始化第一行
        for(int j = 1; j <= amount; j++) dp[0][j] = -1;

        // 从上往下, 必须从左往右. 第二个for循环从 1 开始
        // 硬币下标是从 0 开始, 所以有映射关系. 要减 1
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                // 不选第 i 个硬币
                dp[i][j] = dp[i - 1][j];
                // 选第 i 个硬币.
                if(j - coins[i - 1] >= 0 && dp[i][j- coins[i - 1]] != -1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j- coins[i - 1]] + 1);
                }
            }
        }
        // 前n个硬币中挑选，总金额恰好等于 j 时，所有的选法中, 最小的硬币数是多少
        return dp[n][amount];
    }
}
